package com.klun.project.common.constans;


public class SortTest {

	public static void main(String[] args) {
		SortTest sortTest = new SortTest();
//		sortTest.printArr(sortTest.sortMP());
		sortTest.printArr(sortTest.sortGB());
	}

	public void printArr(Object[] tArr) {
		for (Object t : tArr) {
			System.out.print(String.valueOf(t) + ",");
		}
		System.out.println(";");
	}

	// 冒泡排序
	public Integer[] sortMP() {
		Integer[] arr = {2, 3, 100, 50, 30, 60, 9, 6, 8, 1, 7};
		for (int i = 0; i < arr.length; i++) {
			Integer temp = arr[0];
			for (int j = 1; j < arr.length - i; j++) {
				if (temp > arr[j]) {
					arr[j - 1] = arr[j];
					arr[j] = temp;
				} else if (temp < arr[j]) {
					temp = arr[j];
				}
			}
			printArr(arr);
		}
		return arr;
	}

	// 归并排序
	public Integer[] sortGB() {
		Integer[] arr = {2, 3, 100, 50, 30, 60, 9, 6, 8, 1, 7};
		Integer[] temp = new Integer[arr.length];
		sortGBDG(arr, temp, 0, arr.length - 1);
		return arr;

	}

	public void sortGBDG(Integer[] arr, Integer[] temp, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			sortGBDG(arr, temp, left, mid);
			sortGBDG(arr, temp, mid + 1, right);
			mergeGB(arr, temp, left, mid, right);
		}
	}

	// 归并两个有序指针
	public void mergeGB(Integer[] arr, Integer[] temp, int left, int mid, int right) {
		System.out.println("一次递归");
		int i = left; // 左序列指针
		int j = mid + 1; // 右序列指针
		int t = 0; // 临时数组指针
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}
		while (i <= mid) {
			temp[t++] = arr[i++];
		}
		while (j <= right) {
			temp[t++] = arr[j++];
		}
		// 将temp中的元素全部拷贝到原数组中
		t = 0;
		while (left <= right) {
			System.out.println(left + ":" + t);
			arr[left++] = temp[t++];
		}
		printArr(temp);
		printArr(arr);
	}

}
